#include <iostream>
#include <unordered_set>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    /*
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> cycle_set;
        while (head != NULL) {
            if (cycle_set.count(head) == 1) {
                return true;
            }
            cycle_set.insert(head);
            head = head->next;
        }
        return false;
    }*/
    bool hasCycle(ListNode *head) {
        if (head == NULL) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == NULL || fast->next == NULL) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};


int main() {
    ListNode l1(3), l2(2), l3(0), l4(-4);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = &l2;
    Solution solution;
    bool out = solution.hasCycle(&l1);
    cout << out;
    return 0;
}